package cn.zifangsky.queue;

import cn.zifangsky.linkedlist.SinglyNode;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;

/**
 * 基于单链表实现的队列
 * @author zifangsky
 * @param <K>
 */
public class LinkQueue<K> implements Queue<K>{
	private SinglyNode<K> frontNode; //队首节点
	private SinglyNode<K> rearNode; //队尾节点
	private List<K> list = new ArrayList<>();

	public LinkQueue() {
		frontNode = null;
		rearNode = null;
	}

	/**
	 * 返回队列是否为空
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public boolean isEmpty(){
		return (frontNode == null);
	}

	/**
	 * 返回存储在队列的元素个数
	 * @时间复杂度 O(n)
	 * @return
	 */
	@Override
	public int size(){
		int length = 0;
		SinglyNode<K> currentNode = frontNode;
		while (currentNode != null) {
			length++;
			currentNode = currentNode.getNext();
		}

		return length;
	}

	/**
	 * 入队：在链表表尾插入数据
	 * @时间复杂度 O(1)
	 * @param data
	 */
	@Override
	public void push(K data){
		SinglyNode<K> newNode = new SinglyNode<K>(data);

		if(rearNode != null){
			rearNode.setNext(newNode);
		}

		rearNode = newNode;

		if(frontNode == null){
			frontNode = rearNode;
		}
	}

    /**
     * 入队：在链表表尾插入数据
     * @时间复杂度 O(n)
     * @param data data
     */
    @Override
    public void pushIfNotExist(K data){
        //如果队列中已经存在，则不再入队
        if(list.contains(data)){
            return;
        }

        SinglyNode<K> newNode = new SinglyNode<K>(data);

        if(rearNode != null){
            rearNode.setNext(newNode);
        }

        rearNode = newNode;
        list.add(data);

        if(frontNode == null){
            frontNode = rearNode;
        }
    }

	/**
	 * 出队：删除表头节点
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public K pop(){
		if(isEmpty()){
			throw new RuntimeException("Queue Empty!");
		}else{
			K result = frontNode.getData();

			if(frontNode == rearNode){
				frontNode = null;
				rearNode = null;
			}else{
				frontNode = frontNode.getNext();
			}

			return result;
		}
	}

	/**
	 * 返回队首的元素，但不删除
	 * @时间复杂度 O(1)
	 */
	@Override
	public K top() {
		if(isEmpty()){
			throw new RuntimeException("Queue Empty!");
		}else{
			return frontNode.getData();
		}
	}

	@Override
	public void clear() {
		frontNode = null;
		rearNode = null;
	}

	/**
	 * 遍历队列
	 * @时间复杂度 O(n)
	 * @return
	 */
	@Override
	public void print(Consumer<K> consumer) {
		SinglyNode<K> tmpNode = frontNode;
		while (tmpNode != null) {
			consumer.accept(tmpNode.getData());
			tmpNode = tmpNode.getNext();
		}
	}

	/**
	 * 删除整个队列
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public void deleteQueue() {
		frontNode = null;
		rearNode = null;
	}

}
